#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
const long long inf=1e18;
struct rds{
	int l,r,d;
}qq[N];
int n,q,o,rt[N],maxn[N],lg[N];
long long dp[N];
vector<int>p[N];
struct seg{
	struct node{
		int ls,rs,vl;
		long long vl2,vl3;
	};
	node t[40*N];
	int length;
	void push_up(int k)
	{
		t[k].vl=t[t[k].ls].vl+t[t[k].rs].vl,t[k].vl2=t[t[k].ls].vl2+t[t[k].rs].vl2,t[k].vl3=t[t[k].ls].vl3+t[t[k].rs].vl3;
		return;
	}
	int add(int k,int L,int R,int x,int d1,int d2,int d3)
	{
		int nw=++length;
		t[nw]=t[k];
		if (L==R)
		{
			t[nw].vl+=d1,t[nw].vl2+=d2,t[nw].vl3+=d3;
			return nw;
		}
		int mid=(L+R)>>1;
		if (x<=mid) t[nw].ls=add(t[nw].ls,L,mid,x,d1,d2,d3);
		else t[nw].rs=add(t[nw].rs,mid+1,R,x,d1,d2,d3);
		push_up(nw);
		return nw;
	}
	long long query(int k,int L,int R,int l,int r,int d1,int d2,int d3)
	{
		if (!t[k].vl) return 0;
		if (L==l&&R==r) return 1ll*t[k].vl*d1+t[k].vl2*d2+t[k].vl3*d3;
		int mid=(L+R)>>1;
		if (r<=mid) return query(t[k].ls,L,mid,l,r,d1,d2,d3);
		else if (l>=mid+1) return query(t[k].rs,mid+1,R,l,r,d1,d2,d3);
		else return query(t[k].ls,L,mid,l,mid,d1,d2,d3)+query(t[k].rs,mid+1,R,mid+1,r,d1,d2,d3);
	}
};
seg T;
long long qr(int l1,int r1,int l2,int r2,int d1,int d2,int d3){
	return T.query(rt[r1],1,n,l2,r2,d1,d2,d3)-T.query(rt[l1-1],1,n,l2,r2,d1,d2,d3);
}long long F(int l,int r){
	if(l>r)return inf;
	long long s=0;
	s+=qr(1,l,r,n,1,0,0);
	s+=qr(l,n,1,r,r-l,1,-1);
	int mid=(l+r)>>1;
	s+=qr(mid+1,r,r+1,n,r+1,-1,0);
	s+=qr(l+1,mid,r+1,n,-l,1,0);
	mid=(l+r+1)>>1;
	s+=qr(1,l-1,l,mid-1,-l+1,0,1);
	s+=qr(1,l-1,mid,r-1,r,0,-1);
	return dp[l-1]+s;
}int main(){
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int l,r,ps;
	for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;
	cin>>n>>q;n--;
	while(q--){
        cin>>l>>r;
        p[l].push_back(r-1);
	}for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(auto x:p[i])rt[i]=T.add(rt[i],1,n,x,1,i,x);
	}for(int i=1;i<=n;i++){
		while(o&&F(i,qq[o].l)<F(qq[o].d,qq[o].l))o--;
		if(o&&F(i,qq[o].r)<F(qq[o].d,qq[o].r)){
			ps=qq[o].r;
			for (int j=lg[qq[o].r-qq[o].l];j>=0;--j)
				if (ps-(1<<j)>qq[o].l&&F(i,ps-(1<<j))<F(qq[o].d,ps-(1<<j)))
					ps-=(1<<j);
			qq[o].r=ps-1;
		}ps=qq[o].r;
		if(ps+1<=n)qq[++o]=(rds){ps+1,n,i};ps=0;
		for(int j=lg[o];j>=0;--j)
			if (ps+(1<<j)<=o&&qq[ps+(1<<j)].l<=i)
				ps+=(1<<j);
		dp[i]=F(qq[ps].d,i);
	}cout<<dp[n]<<"\n";
	return 0;
}
